package datastructure.graph.最短路径;

import datastructure.tree.IndexMinPQ;

import java.util.Stack;

/**
 * @author MaoLin Wang
 * @description
 * @date 2020/8/28 3:11 下午
 */
public class DijkstraSP {
    private DirectedEdge[] edgeTo;
    private double[] distTo;
    private IndexMinPQ<Double>pq;

    public DijkstraSP(EdgeWeightedDigraph graph, int s) {
        edgeTo=new DirectedEdge[graph.V()];
        distTo=new double[graph.V()];
        pq=new IndexMinPQ<>(graph.V());

        for (int i = 0; i < graph.V(); i++) {
            distTo[i]=Double.MAX_VALUE;
        }
        distTo[s]=0.0;
        pq.insert(s,distTo[s]);
        while (!pq.isEmpty()){
            relax(graph,pq.delMin());
        }
    }

    private void relax(EdgeWeightedDigraph graph,int v) {

        for (DirectedEdge edge : graph.adj(v)) {
            int to = edge.to();
            if (distTo[to]>distTo[v]+edge.weight()){
                distTo[to]=distTo[v]+edge.weight();
                edgeTo[to]=edge;
                if (pq.contains(to)){
                    pq.changeKey(to,distTo[to]);
                }else {
                    pq.insert(to,distTo[to]);
                }
            }
        }
    }

    /**
     * 从起点到顶点v的最短路径权值
     * @param v
     * @return
     */
    public double distTo(int v){
        return distTo[v];
    }

    /**
     * 是否存在从s到v的最短路径
     * @param v
     * @return
     */
    public boolean hasPathTo(int v){
        return distTo[v]<Double.POSITIVE_INFINITY;
    }

    /**
     * 返回从s到v的最短路径
     * @param v
     * @return
     */
    public Iterable<DirectedEdge> pathTo(int v){
        if (!hasPathTo(v))return null;
        Stack<DirectedEdge> path=new Stack<>();
        for (DirectedEdge edge=edgeTo[v];edge!=null;edge=edgeTo[edge.from()])
        {
            path.push(edge);
        }
        return path;
    }

    public static void main(String[] args) {
        
        EdgeWeightedDigraph graph=new EdgeWeightedDigraph(8);
        graph.addEdge(new DirectedEdge(4,5,0.35));
        graph.addEdge(new DirectedEdge(4,7,0.37));
        graph.addEdge(new DirectedEdge(5,7,0.28));
        graph.addEdge(new DirectedEdge(0,7,0.16));
        graph.addEdge(new DirectedEdge(1,5,0.32));
        graph.addEdge(new DirectedEdge(0,4,0.38));
        graph.addEdge(new DirectedEdge(2,3,0.17));
        graph.addEdge(new DirectedEdge(1,7,0.19));
        graph.addEdge(new DirectedEdge(0,2,0.26));
        graph.addEdge(new DirectedEdge(1,2,0.36));
        graph.addEdge(new DirectedEdge(1,3,0.29));
        graph.addEdge(new DirectedEdge(2,7,0.34));
        graph.addEdge(new DirectedEdge(6,2,0.40));
        graph.addEdge(new DirectedEdge(3,6,0.52));
        graph.addEdge(new DirectedEdge(6,0,0.58));
        graph.addEdge(new DirectedEdge(6,4,0.93));
        
        DijkstraSP sp=new DijkstraSP(graph,0);
        Iterable<DirectedEdge> directedEdges = sp.pathTo(5);
        System.out.println(directedEdges);
    }
}
